package Algorithm.BinaryResearch;

public class BinarySearch {
    public static void main(String[] args) {

    }

    //这是最基本的
    public static int Solution1(int nums[],int taraget){
        int left=0;
        int right = nums.length-1;
        while (left<=right){
            int mid = left +(right-left)/2;
            if (nums[mid]==taraget){
                return mid;
            }else if (nums[mid]<nums[right]){
                right = mid-1;

            }else {
                left = left+1;
            }
        }
        return left;
    }

    // https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-3tong-yong-er-fen-mo-ban-by-lu-ch-ialr/
    // 查找 第一个 >= target 的位置，不存在则返回 n
    public int binarySearch2(int[] nums, int target) {
        // 范围：[0, n - 1] + [n表示不合法]
        int left = 0;
        int right = nums.length;
        while (left < right) {
            int mid = (left + right) >> 1;
            // 合法，要在合法值中找最小的，继续往左找，范围缩小为 [left, mid]，注意要包含合法值 mid
            if (nums[mid] >= target) {
                right = mid;
            } else {
                left = mid + 1; // 不合法，范围缩小为 [mid + 1, right]
            }
        }
        return right;
    }

    // 最后一个 <= target 的位置，不存在则返回 -1
    public int binarySearch3(int[] nums, int target) {
        // 范围：[-1表示不合法] + [0, n - 1]
        int left = -1;
        int right = nums.length - 1;
        while (left < right) {
            // +1 向上取整，避免死循环
            int mid = (left + right + 1) >> 1;
            // 合法，要在合法值中找最大的，继续往右找，范围缩小为 [mid, right]，注意要包含合法值 mid
            if (nums[mid] <= target) {
                left = mid;
            } else {
                right = mid - 1; // 不合法，范围缩小为 [left, mid - 1]
            }
        }
        return left;
    }

}
